import java.util.Stack;

/*
剑指 Offer 31. 栈的压入、弹出序列
解题思路：模拟法，每放入一个数字到栈中就进行一次判断，符合条件就出栈，最后返回栈是否为空
 */
public class Offer31 {

  public static void main(String[] args) {
    int[] one = new int[]{1,2,3,4,5};
    int[] two = new int[]{5,4,3,2,1};
    System.out.println(validateStackSequences(one, two));
  }

  public static boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int i = 0;
    for (int num : pushed) {
      stack.push(num);
      while (!stack.isEmpty() && stack.peek() == popped[i]){
        stack.pop();
        i++;
      }
    }
    return stack.isEmpty();
  }
}
